package com.atguigu.search;

import java.util.Arrays;

/*
* 斐波纳妾查找方法
* 对于F(k-1)的理解
*   1.由于斐波那契数列F(k)=F(k-1)+F(k-2)的性质，只要是数列长度为F(k)-1的长度，可以得到就可以把数列分为F(k-1)-1和F(k-2)-1的长度，
*   从而中间位置为mid=low+F(k-1)-1
*   2.类似的，每一段都可以用相同的方式分割
*   3.但是顺序表的长度不一定刚好等于F(k)-1,所以将原来的数列长度n增加到F(k)-1,新增加的位置，都赋值为n位置的值就行了
*
*
* */
public class FibonacciSearch {
    static int maxSize=20;
    public static void main(String[] args) {

        int[] arr={1,8,10,89,1000,1234};
        int i = fibonacciSearch(arr,1234);
        System.out.println("i = " + i);

    }
    //因为后面要用到mid=low+F(k-1)-1,需要使用到斐波那契额数列，我们先获得一个斐波那契额数列
    //递归得到斐波那契额数列
    public static int[] fib(){
        int[] f=new int[maxSize];
        f[0]=1;
        f[1]=1;
        for (int i = 2; i <maxSize ; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
    //编写斐波那契查找算法
    //非递归的方法
    public static int fibonacciSearch(int[] arr,int key){
        int low=0;
        int high=arr.length-1;
        int k=0;//斐波那契额数列的下表，没有返回-1
        int f[]=fib();
        while (high>f[k]-1){
            k++;
        }
        //将我们的数组arr，增加到f(k)的长度
        int[] temp= Arrays.copyOf(arr,f[k]);
        //把arr.length到f[k]-1，位置的值都写成arr[arr.length-1]
        for(int i=high+1;i<f[k];i++){
            temp[i]=arr[high];
        }
        //写好之后，我们计算mid的值
        while (low<=high){
            int mid=low+f[k-1]-1;
            if(key>temp[mid]){
                //说明寻找的值在mid的右边此时low为mid+1
                //而右边yo有f[k-2]-1个数字说明k=-2;
                low=mid+1;
                k-=2;
            }else if(key<temp[mid]){
                //key在mid的左边，此时low不变
                //而左边有f[k-1]-1个数字，说明k-=1
                high=mid-1;
                k-=1;
            }else{
                if(high>=mid){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}
